import java.util.*;

public class Demo11 {


/*
    public static void main(String[] args) {
        int[] arr = {1,2,3,2,2};
        getValue(arr,5);
    }
    public static int getValue(int[] gifts, int n) {
        HashMap<Integer,Integer> hashMap = new HashMap<>();
        for(int i=0;i<gifts.length;i++){
            if (hashMap.containsKey(gifts[i])){
                hashMap.put(gifts[i], hashMap.get(gifts[i])+1);
            }else{
                hashMap.put(gifts[i], 1);
            }
        }
        for(Integer x:hashMap.keySet()){
            if (hashMap.get(x)>n){
                return x;
            }
        }
        return 0;




    }
*/



/*    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        String str = in.nextLine();
        int[] hash = new int[128];
        for(int i = 0;i<128;i++){
            hash[i] = -1;
        }
        for(int i = 0;i<str.length();i++){
            hash[str.charAt(i)]++;
        }

        String ret = "";
        for(int i = 0;i<128;i++){
            if (hash[i]==0){
                ret+=(char)i;
            }
        }
        int index = str.length();
        for(int i = 0;i<ret.length();i++){
            index = Math.min(index,str.indexOf(ret.charAt(i)));
        }
        if(index<str.length()){
            System.out.println(str.charAt(index));
        }else{
            System.out.println(-1);
        }
    }*/




/*    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        for(int k = 0;k<2;k++){
            int n = in.nextInt();
            int a = in.nextInt();
            int[] arr = new int[n];
            for(int i = 0;i<n;i++){
                arr[i] = in.nextInt();
            }
            //开始打怪
            int count = a;
            for(int i = 0;i<n;i++){
                if (count>=arr[i]){
                    count+=arr[i];
                }
                if (count<arr[i]){
                    int x1 = count;
                    int x2 = arr[i];
                    while (x2%x1!=0){
                        int tmp = x2%x1;
                        x2 = x1;
                        x1 = tmp;
                    }
                    count+=x1;
                }

            }
            System.out.println(count);

        }



    }*/










    /*public static void main(String[] args) {
        Scanner in = new Scanner(System.in);

        String n1 = in.nextLine();
        String str = in.nextLine();

        int n = Integer.parseInt(n1);

        int[] arr = {1,2,3,4};
        int index = 1;



        for(int i = 0;i<str.length();i++){
            if (str.charAt(i)=='U'){
                index--;
                if (index==0){
                    index = n;
                    for(int j = 0;j<4;j++){
                        arr[j] = n-3+j;
                    }
                }else{
                    if (index<arr[0]){
                        for(int j=0;j<4;j++){
                            arr[j]--;
                        }
                    }
                }

            }else{
                index++;
                if (index==n+1){
                    index = 1;
                    for(int j = 0;j<4;j++){
                        arr[j] = j+1;
                    }
                }else{
                    if (index>arr[3]){
                        for(int j = 0;j<4;j++){
                            arr[j]++;
                        }
                    }
                }
            }
        }

        for(int i = 0;i<4;i++){
            System.out.print(arr[i] +" ");
        }
        System.out.println();
        System.out.println(index);




    }


*/




//
//    public static void main(String[] args) {
//        Scanner in = new Scanner(System.in);
//        int m= in.nextInt(); //输出几次
//
//
//        for(int i = 0;i<m;i++){
//            int n = in.nextInt(); // 每人几张牌
//            int k = in.nextInt();//洗几次牌
//            //输入牌
//            int[] arr = new int[2*n];
//            for(int j = 2*n-1;j>=0;j--){
//                arr[j] = in.nextInt();
//            }
//            //左边人的牌
//            Stack<Integer> left = new Stack<>();
//            //右边人的牌
//            Stack<Integer> right = new Stack<>();
//            //洗几次牌
//            for(int x = 0;x<k;x++){
//                //arr前n张放到left栈
//                //arr后n张放到right栈
//                for(int leftIndex = 2*n-1; leftIndex >=n;leftIndex--){
//                    left.push(arr[leftIndex]);
//                    right.push(arr[leftIndex-n]);
//                }
//                //左右栈依次放到arr中
//                int arrayIndex = 0;
//                while (!left.isEmpty() || !right.isEmpty()) {
//                    arr[arrayIndex++] = right.pop();
//                    arr[arrayIndex++] = left.pop();
//                }
//            }
//            for (int index = 2*n-1; index >=0 ;index--){
//                if (index==0){
//                    System.out.println(arr[index]);
//                }else{
//                    System.out.print(arr[index]+" ");
//                }
//
//            }
//            System.out.println();
//        }
//    }








/*    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        String str1 = in.nextLine();
        String str2 = in.nextLine();
        int len1 = str1.length();
        int len2 = str2.length();

       int count = 0;
        for(int i = 1;i<len1;i++){
            int left = 0;
            int right = left+i;
            while (right<len1){
                String tmp = str1.substring(left,right);
                if (str2.contains(tmp)){
                    count = Math.max(count, right-left);
                }
                right++;
                left++;
            }

        }
        System.out.println(count);

    }*/



/*
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
       String str = in.nextLine();
       StringBuffer ret = new StringBuffer(str);
        System.out.println(ret.reverse());
    }
*/











/*
    public static void main(String[] args) {
        String x = "fmn";
        System.out.println(x);
        x.toUpperCase();
        System.out.println(x);
        String y = x.replace("f", "F");
        System.out.println(x);
        System.out.println(y);
        System.out.println(1 == new Integer(1));
        System.out.println("1".equals(new String("1")));
    }*/

    /*public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        String str1 = in.nextLine();
        String str2 = in.nextLine();


        int len1 = str1.length();
        int len2 = str2.length();

        String ret = "";

        if (len1 <= len2){
            for(int i = 1;i<=len1;i++){
                int left = 0;
                int right = left+i;
                while (right<len1){
                    //str1的子串
                    String tmp = str1.substring(left, right+1);
//                    System.out.println(tmp);
                    if (str2.contains(tmp)){
                        if (tmp.length()>ret.length()){
                            ret = new String(tmp);
                        }
                    }
                    left++;
                    right++;
                }

            }
        }else{
            for(int i = 1;i<=len2;i++){
                int left = 0;
                int right = left+i;
                while (right<len2){
                    //str2的子串
                    String tmp = str2.substring(left, right+1);
                    if (str1.contains(tmp)){
                        if (tmp.length()>ret.length()){
                            ret = new String(tmp);
                        }
                    }
                    left++;
                    right++;
                }
            }
        }
        System.out.println(ret);






    }
*/






/*    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        // 注意 hasNext 和 hasNextLine 的区别
        while (in.hasNextInt()) { // 注意 while 处理多个 case
            int a = in.nextInt();
            if(a==0){
                break;
            }
            int count = 0;
            int tmp = a;
            while(tmp>1){
                count += tmp/3;
                tmp = tmp%3+tmp/3;
                if (tmp == 2){
                    count++;
                    break;
                }
            }
            System.out.println(count);
        }
    }*/







/*    public int minCost(int[][] costs) {
        int n = costs.length;
        int[][] dp = new int[n+1][3];
        for(int i = 1;i<=n;i++){
            dp[i][0] = Math.min(dp[i-1][1],dp[i-1][2])+costs[i-1][0];
            dp[i][1] = Math.min(dp[i-1][0],dp[i-1][2])+costs[i-1][1];
            dp[i][2] = Math.min(dp[i-1][0],dp[i-1][1])+costs[i-1][2];
        }
        return Math.min(dp[n][0],Math.min(dp[n][1],dp[n][2]));



    }*/



/*    public int deleteAndEarn(int[] nums) {
        int n = nums.length;
        int[] hash = new int[10001];
        int[] g = new int[10001];
        int[] f = new int[10001];
        for(int i = 0;i<n;i++){
            hash[nums[i]]+=nums[i];
        }

        f[0] = hash[0];
        g[0] = 0;
        int len = hash.length;
        for(int i = 1;i<hash.length;i++){
            f[i] = g[i-1]+hash[i];
            g[i] = Math.max(g[i-1],f[i-1]);
        }
        return Math.max(f[len-1],g[len-1]);
    }*/




/*    public int rob(int[] nums) {
        int n = nums.length;
        if (n==0){
            return 0;
        }
        if (n==1){
            return nums[0];
        }
        int[] f = new int[n];
        int[] g = new int[n];

        //偷第一个
        f[0] = nums[0];
        for(int i = 1;i<n-1;i++){
            f[i] = g[i-1]+nums[i];
            g[i] = Math.max(g[i-1],f[i-1]);
        }
        int max = Math.max(f[n-2],g[n-2]);

        //不偷第一个
        f[0] = 0;
        for(int i=1;i<n;i++){
            f[i] = g[i-1]+nums[i];
            g[i] = Math.max(g[i-1],f[i-1]);
        }
        int max2 = Math.max(f[n-1], g[n-1]);
        return Math.max(max, max2);

    }*/






/*    public int massage(int[] nums) {
        int n = nums.length;
        if (n==0){
            return 0;
        }
        int[] f = new int[n];
        int[] g = new int[n];

        f[0] = nums[0];
        g[0] = 0;
        for(int i = 1;i<n;i++){
            f[i] = g[i-1]+nums[i];
            g[i] = Math.max(f[i-1],g[i-1]);
        }
        return Math.max(f[n-1],g[n-1]);



    }*/
















/*    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        String str1 = in.nextLine();
        String str2 = in.nextLine();
        str1 = str1.toLowerCase();
        str2 = str2.toLowerCase();
        int left = 0;
        int right = 0;
        while (left<str1.length() && right < str2.length()){
            if (str1.charAt(left)==str2.charAt(right)){
                left++;
                right++;
            }else if (str1.charAt(left) == '?'){
                left++;
                right++;
            }else if(str1.charAt(left) == '*'){
                if (left<str1.length()-1){
                    if (str1.charAt(left+1)==str2.charAt(right)){
                        left++;
                        left++;
                        right++;
                    }else{
                        right++;
                    }
                } else {
                    for(int i = right;i<str2.length();i++){
                        if ((str2.charAt(i)>='a' && str2.charAt(i)<='z')
                                || (str2.charAt(i) >='0'&& str2.charAt(i)<='9')){

                        }else{
                            System.out.println("false");
                            return;
                        }
                    }
                    System.out.println("true");
                    return;
                }
            }else{
                System.out.println("false");
                return;
            }

        }
        if (left<str1.length() || right < str2.length()){
            System.out.println("false");
        }else{
            System.out.println("true");
        }



    }*/

/*    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        int  n = in.nextInt();
        int a = 1;
        int b = 1;
        int c = 0;
        for(int i = 3;i<=n;i++){
            c = a+b;
            a = b;
            b = c;
        }
        System.out.println(c);

    }*/

/*    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        String str = in.nextLine();
        String c1 = in.nextLine();
        c1 = c1.toLowerCase();
        char c = c1.charAt(0);
        int count = 0;
        str = str.toLowerCase();
        for(int i = 0;i<str.length();i++){
            if (str.charAt(i)==c){
                count++;
            }
        }
        System.out.println(count);



    }*/



/*    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        int n = in.nextInt();
        int m = 2*(n-1)+1;
        int[][] dp = new int[n][n];
        dp[0][n-1]=1;
        int ret = -1;
        for(int i = 1;i<n;i++){
            for(int j = n-i-1;j<i+n;j++){
                if (j>0 && j<n-1){
                    dp[i][j]=dp[i-1][j-1]+dp[i-1][j]+dp[i-1][j+1];
                }
                if (j==0){
                    dp[i][j]=dp[i-1][j+1];
                }
                if (j==n-1){
                    dp[i][j]=dp[i-1][j]+2*dp[i-1][j-1];
                }
            }
        }
        for(int i=0;i<n;i++){
            if (dp[n-1][i]%2==0){
                ret = i+1;
                break;
            }
        }
        System.out.println(ret);

    }*/


/*    public int calculateMinimumHP(int[][] nums) {

        int m = nums.length;
        int n = nums[0].length;
        int[][] dp = new int[m+1][n+1];
        for (int i=0;i<=n;i++){
            dp[m][i]=Integer.MAX_VALUE;
        }
        for(int j = 0;j<=m;j++){
            dp[j][n]=Integer.MAX_VALUE;
        }
        dp[m][n-1] = 1;
        dp[m-1][n] = 1;


        for(int i=m-1;i>=0;i--){
            for(int j=n-1;j>=0;j--){
                dp[i][j] = Math.min(dp[i][j+1],dp[i+1][j])+nums[i][j];
                dp[i][j] = Math.min(dp[i][j],1);
            }
        }
        return dp[0][0];


    }*/








   /* public static void main(String[] args) {

        System.out.println(Integer.toHexString(0x54&0xe8));
        System.out.println(Integer.toHexString(0x54|0x44));
        System.out.println(Integer.toHexString(0x3e^0xe8));
        System.out.println(Integer.toHexString(~0x78));
        System.out.println(Integer.toHexString(0x6f<<2));
        System.out.println(Integer.toHexString(0x7d>>3));



    }
*/



/*    public int minPathSum(int[][] grid) {
        int m = grid.length;
        int n = grid[0].length;
        int[][] dp = new int[m+1][n+1];
        for(int i=0;i<=m;i++){
            dp[i][0]=Integer.MAX_VALUE;
        }
        for(int i=0;i<=n;i++){
            dp[0][i]=Integer.MAX_VALUE;
        }

        for(int i = 1;i<=m;i++){
            for(int j = 1;j<=n;j++){
                if(i==1&&j==1){
                    dp[i][j]=grid[i-1][j-1];
                }else{
                    dp[i][j] = Math.min(dp[i][j-1],dp[i-1][j])+grid[i-1][j-1];
                }
            }
        }
        return dp[m][n];
    }*/


  /*  public int minFallingPathSum(int[][] matrix) {
        int m = matrix.length;
        int n = matrix[0].length;
        int[][] dp = new int[m+1][n+2];
        for(int i=1;i<=m;i++){
            dp[i][0]=Integer.MAX_VALUE;
            dp[i][n+1]=Integer.MAX_VALUE;
        }
        int min = Integer.MAX_VALUE;
        for(int i = 1;i<=m;i++){
            for(int j = 1;j<=n;j++){
                dp[i][j] = getmin(dp[i-1][j-1],dp[i-1][j],dp[i-1][j+1])+matrix[i-1][j-1];
                if(i==m){
                    min = Math.min(min,dp[i][j]);
                }
            }
        }
        return min;
    }

    private int getmin(int a, int b, int c) {
        int tmp = a<b?a:b;
        tmp = tmp<c?tmp:c;
        return tmp;

    }*/


   /* public int jewelleryValue(int[][] nums) {
        int m = nums.length;
        int n = nums[0].length;
        int[][] dp = new int[m+1][n+1];
        for(int i = 1;i<=m;i++){
            for(int j = 1;j<=n;j++){
                dp[i][j] = Math.max(dp[i-1][j]+nums[i-1][j-1],dp[i][j-1]+nums[i-1][j-1]);
            }
        }
        return dp[m][n];
    }

*/



/*    public int uniquePathsWithObstacles(int[][] nums) {
        int m = nums.length;
        int n = nums[0].length;
        int[][] dp = new int[m+1][n+1];
        dp[1][0] = 1;
        for(int i =1;i<=m;i++){
            for(int j=1;j<=n;j++){
                if (nums[i-1][j-1] == 0){
                    dp[i][j] = dp[i-1][j]+dp[i][j-1];
                }if (nums[i-1][j-1] == 1){
                    dp[i][j]=0;
                }
            }
        }

        return dp[m][n];


    }*/



   /* public int uniquePathsWithObstacles(int[][] nums) {
        int m = nums.length;
        int n = nums[0].length;
        int[][] matrix = new int[m][n];
        for(int i = 0;i<m;i++){
            for(int j = 0;j<n;j++){
                if (i==0 && nums[i][j] ==0){
                    matrix[i][j]=1;
                    continue;
                }
                if (j==0 && nums[i][j]==0){
                    matrix[i][j] =1;
                    continue;
                }
                if (nums[i][j]==1){
                    matrix[i][j] = 0;
                    continue;
                }
                if (nums[i][j] == 0){
                    matrix[i][j] = matrix[i-1][j]+matrix[i][j-1];
                }

            }
        }

        return matrix[m-1][n-1];

    }*/













   /* public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        int n = in.nextInt();
        int a = 0;
        int b = 1;
        int c = 1;
        while (c<n){
            a=b;
            b=c;
            c=a+b;
        }
        System.out.println(Math.min(c-n, n-b));




    }*/

    /*public boolean chkParenthesis(String A, int n) {

        if(n%2!=0){
            return false;
        }
        int a = 0;
        for(char c:A.toCharArray()){
            if (c=='('){
                a++;
            }else if (c ==')'){
                a--;
            }else{
                return false;
            }

        }
        if (a==0){
            return true;
        }

        return false;
    }*/


/*
    public static void main(String[] args) {
         Scanner in = new Scanner(System.in);
         String str = in.nextLine();
         String left = str.split("-")[0];
         String right = str.split("-")[1];
         //两边都是1 2 3的情况,比较 1 2 3的情况
         int l = left.replaceAll(" ","").replaceAll("0","").length();
         int r = right.replaceAll(" ","").replaceAll("0","").length();
//        System.out.println(left);
//        System.out.println(right);
         HashMap<Character,Integer> hash = new HashMap<>();
         for(int i=3;i<=10;i++){
             hash.put((char)(i+'0'),i);
         }
         hash.put((char)(10+'0'),10);
         hash.put('J',11);
         hash.put('Q',12);
         hash.put('K',13);
         hash.put('A',14);
         hash.put('2',15);

         if (l=="joker".length()){
             System.out.println(left);
             return;
         }
         if (r=="joker".length()){
             System.out.println(right);
             return;
         }

         if ((l<=3 && l==r) || (l==5 && l==r)){
             if (hash.get(left.charAt(0))>hash.get(right.charAt(0))){
                 System.out.println(left);
                 return;
             }else{
                 System.out.println(right);
                 return;
             }


         }

         //两边是四个炸弹有炸弹情况
        if (l==4 && r==4){
            if (left.charAt(0)>right.charAt(0)){
                System.out.println(left);
                return;
            }else{
                System.out.println(right);
                return;
            }
        }

        //有大小王的
        if (l=="jokerJOKER".length() || r=="jokerJOKER".length()){
            System.out.println("joker JOKER");
            return;
        }

        //一边又四个炸弹，一边是 1 2 3 张排
        if (l==4){
            System.out.println(left);
            return;
        }
        if (r==4){
            System.out.println(right);
            return;
        }
        System.out.println("ERROR");

    }*/


   /* public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        int n = in.nextInt();
        int count = 0;

        for(int i = 2;i<=n;i++){
            int sum = 0;
            for(int j = 1;j<i;j++){
                if (i%j==0){
                    sum+=j;
                }
                if (sum>i){
                    break;
                }
            }
            if(sum==i){
                count++;
            }
        }
        System.out.println(count);
    }
*/


/*    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        int w = in.nextInt();
        int h = in.nextInt();
        int count = 0;
        int[][] array = new int[w][h];
        for(int i = 0;i<w;i++){
            for(int j = 0;j<h;j++){
                if (array[i][j] ==0){
                    count++;
                    if (i+2<w){
                        array[i+2][j] = 1;
                    }
                    if (j+2<h){
                        array[i][j+2] = 1;
                    }
                }
            }
        }
        System.out.println(count);

    }*/




/*

    public int StrToInt(String str) {
        char[] chs = str.toCharArray();
        if (chs == null || chs.length==0){
            return 0;
        }
        int flag = 1;
        if (chs[0] == '-') {
            flag = -1;
            chs[0]='0';
        }else if (chs[0]=='+'){
            flag = 1;
            chs[0]='0';
        }

        int sum = 0;
        for(int i=0;i<str.length();i++){
            if (chs[i]<'0' || chs[i]>'9'){
                sum = 0;
                break;
            }
            sum = sum*10+(chs[i]-'0');
        }
        if (flag==1){
            return sum;
        }else if(flag==-1){
            return sum*-1;
        }
        return sum;

    }

*/












/*    public static void main(String[] args) {

        Scanner in = new Scanner(System.in);
        while (in.hasNextInt()) { // 注意 while 处理多个 case
            int count = 0;
            int a = in.nextInt();
            while (a!=0){
                if (a%2==1){
                    count++;
                }
                a/=2;
            }
            System.out.println(count);
        }

    }*/
















  /*  public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        int size = in.nextInt();
        int[] array = new int[size];

        for(int i =0;i<size;i++){
            array[i] = in.nextInt();
        }

        int sum = array[0];
        int max = array[0];
        for (int i=1;i<size;i++){
            sum = Math.max(sum+array[i],array[i]);
            max = Math.max(max,sum);
        }

        System.out.println(max);
    }
*/

   /* public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        String  str1 = in.nextLine();
        String  str2 = in.nextLine();

        int count = 0;
        int len = str1.length();
        for(int i=0;i<=len;i++){
            StringBuffer str = new StringBuffer(str1);
            str.insert(i,str2);
            StringBuffer str4 = new StringBuffer(str);
            StringBuffer str5 = str4.reverse();
            if (str5.toString().equals(str.toString())){
                count++;
            }
        }
        System.out.println(count);

    }*/






}
